package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/count-numbers-with-unique-digits/description

357. 统计各位数字都不同的数字个数
给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。

示例 1：
输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。

示例 2：
输入：n = 0
输出：1

提示：
0 <= n <= 8
 */

class leetcode_357 {
    @Test
    fun test_1() {
        val actual = countNumbersWithUniqueDigits(2)
        val expected = 91
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val actual = countNumbersWithUniqueDigits(0)
        val expected = 1
        Assert.assertEquals(expected, actual)
    }

    private fun countNumbersWithUniqueDigits(n: Int): Int {
        if (n == 0) {
            return 1
        }
        if (n == 1) {
            return 10
        }
        collect(n, "")
        return count
    }

    private var count: Int = 0
    fun collect(n: Int, path: String) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        // 终止条件
        if (0 < path.length && path.length <= n) {
            // 收集结果
            count++
            if (path.length == n) {
                return
            }
        }

        // 3  确定单层递归的处理逻辑
        for (i in 0..9) {
            // 处理节点
            // 树层去重、树枝去重
            if (path.contains("" + i)) {
                continue
            }
            if (path == "0") { // 0XXX?
                break
            }
            val newPath = path + i
            // println(newPath)

            // 递归
            collect(n, newPath)

            // 回溯

            // 去重？剪枝？
        }
    }
}
